/*-------- Includes --------*/
#include <stdio.h>
#include <stdlib.h>

/*-------- Types --------*/
template<class T> class Node {
public:
    T       data;
    Node<T> *next;

public:
    Node()                 { next = NULL;        }
    Node(Node<T> *n)       { next = n;           }
    Node(T &d, Node<T> *n) { data = d; next = n; }
};

template<class E> class LinkedQueue {
private:
    Node<E> *head;
    Node<E> *tail;
    int     size;

public:
    // Construtors
    LinkedQueue() { tail = new Node<E>(); head = new Node<E>(tail); size = 0; }
    // Deconstructors
    ~LinkedQueue();

    // Methods
    bool isEmpty() { return head->next == tail; }
    int  getSize() { return size;               }

    void enqueue(E &e);
    E    dequeue();
    E    peek();
};

/*-------- Function prototypes --------*/
template<class T> void destroy(Node<T> *p);

/*-------- Main Test --------*/
int main(int argc, const char *argv[])
{
    LinkedQueue<int> queue;

    for (int i = 1; i < 100; i++) {
        if (i % 3 == 0) queue.dequeue();
        else            queue.enqueue(i);
    }

    printf("size = %d\n", queue.getSize());

    while (!queue.isEmpty())
        printf("%d ", queue.dequeue());
    putchar('\n');
}

/*-------- Functions --------*/
/* LinkedQueue::Methods */
template<class E>
LinkedQueue<E>::~LinkedQueue() { destroy(head); }

template<class E>
void LinkedQueue<E>::enqueue(E &e)
{
    tail->data = e;
    tail->next = new Node<E>();

    // update
    tail = tail->next;
    size++;
}

template<class E>
E LinkedQueue<E>::dequeue()
{
    // if queue is empty, then exit
    if (isEmpty()) {
        fprintf(stderr, "Error: queue underflow\n");
        exit(1);
    }

    // retrieve element
    E e = head->next->data;

    // save head node
    Node<E> *p = head->next;

    // update
    head->next = head->next->next;
    size--;

    delete p;

    return e;
}

template<class E>
E LinkedQueue<E>::peek()
{
    // if queue is empty, then exit
    if (isEmpty()) {
        fprintf(stderr, "Error: queue underflow\n");
        exit(1);
    }

    return head->next->data;
}
/* LinkedQueue::End */

template<class T> void destroy(Node<T> *p)
{
    // destroy recursively
    if (p->next != NULL) destroy<T>(p->next);

    delete p;
}
